package base.sort;

/**
 * 描述：
 *      小和问题
 * @author hl
 * @version 1.0
 * @date 2020/10/23 16:01
 */
public class Code_05_SmallSum {
    public static void main(String[] args) {
        int[] arr = {1,3,4,2,5};
        System.out.println(new Code_05_SmallSum().smallSum(arr));
    }
    public int smallSum(int[] arr){
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

    private int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 2);
//        mergeSort(arr, l, mid);//求出左边的小和
//        mergeSort(arr, mid+1, r);//求出右边的小和
        return mergeSort(arr, l, mid)
                + mergeSort(arr, mid+1, r) + merge(arr, l, mid, r);
    }

    private int merge(int[] arr, int l, int mid, int r) {
        int[] helper = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res = 0;//用于记录此次合并中产生的小和
        while(p1 <= mid && p2 <= r){
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            helper[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            helper[i++] = arr[p1++];
        }
        while(p2 <= r){
            helper[i++] = arr[p2++];
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l+j] = helper[j];
        }
        return res;
    }
}
